package test;

import java.util.BitSet;

class Hash {
    public int cap;//容量
    public int seed;//种子

    public Hash(int cap, int seed) {
        this.cap = cap;
        this.seed = seed;
    }

    //把当前字符串变成一个hash值
    public int hash(String key) {
        int h;
        return (key == null) ? 0 : (seed * (cap - 1)) & ((h = key.hashCode()) ^ (h >>> 16));
    }
}

public class MyBloomFilter {
    public static final int DEFAULT_SIZE = 1 << 20;
    public BitSet bitSet;
    public int usedSize;
    public static final int[] seeds = {5, 7, 11, 13, 27, 33};
    public Hash[] hashes;

    public MyBloomFilter() {
        bitSet = new BitSet(DEFAULT_SIZE);
        hashes = new Hash[seeds.length];
        for (int i = 0; i < hashes.length; i++) {
            hashes[i] = new Hash(DEFAULT_SIZE, seeds[i]);
        }
    }

    public void add(String val) {
        for (Hash hash : hashes) {
            int index = hash.hash(val);
            bitSet.set(index);
        }
        usedSize++;
    }

    public boolean contains(String val) {
        for (Hash hash : hashes) {
            int index = hash.hash(val);
            boolean flag = bitSet.get(index);
            if (!flag) {
                return false;
            }
        }
        return true;//会误判
    }

    public static void main(String[] args) {
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        myBloomFilter.add("hello");
        myBloomFilter.add("hello1");
        myBloomFilter.add("haha");
        System.out.println(myBloomFilter.contains("hello"));
        System.out.println(myBloomFilter.contains("hello1"));
        System.out.println(myBloomFilter.contains("hello2"));
    }
}
